package com.smday.sort;

import com.sun.corba.se.internal.Interceptors.PIORB;

import java.util.Arrays;

/**
 * @author Summerday
 */
public class QuickSort {

    public static void main(String[] args) {

        int[]arr = {2,5,1,3,6};
        quickSort(arr);

        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(int[]arr){
        quickSort(arr,0,arr.length-1);

    }

    public static void quickSort(int[] arr,int start,int end){


        if(start<end){

            int pivotIndex = partition(arr,start,end);
            System.out.printf("pivotIndex = %d , start = %d , end = %d \n", pivotIndex,start,end);

            quickSort(arr,start,pivotIndex);
            quickSort(arr,pivotIndex+1,end);


        }


    }

    private static int partition(int[] arr, int start, int end) {

        int pivot = arr[start];

        while(start<end){


            while(start<end&&arr[end]>= pivot){

                end--;

            }
            arr[start] = arr[end];

            while(start<end&&arr[start]<=pivot){
                start++;
            }
            arr[end] = arr[start];


        }
        arr[start] = pivot;
        return start;
    }

}
